package e_ch13_directedG.topoSort;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

import e_ch13_directedG.graph_final.Graph_final_try;

public class TopoSort_try {
	
	private int[] temp_indegree;
	private Graph_final_try g;
	private ArrayList<Integer> ret;
	private boolean hasCycle;
	
	public TopoSort_try(Graph_final_try graph) {
		if(!graph.isDirected()) throw new IllegalArgumentException("function only for the directed");
		
		this.g = graph;
		ret = new ArrayList<>();
		temp_indegree = new int[g.getV()];
		for (int i = 0; i < temp_indegree.length; i++) {
			temp_indegree[i] = g.indegree(i);
		}
		
		LinkedList<Integer> q = new LinkedList<>(); //所有的可出发点； 从任意一个出发，走到其他出发点指向的顶点 都会停下来，选择了一个出发点后，其他可出发点就成了关卡；
		
		//找初始可出发点
		for (int i = 0; i < temp_indegree.length; i++)
				if(temp_indegree[i] == 0)  
					q.add(i);
		
		while(!q.isEmpty()) { //可出发点用完了 表示 只要是DAG 就已经过完所有顶点了
			int cur = q.poll();
			ret.add(cur);
			
			for (int v : g.adj(cur)) {   
				temp_indegree[v] --;
				if(temp_indegree[v] == 0)  //过完的顶点相当于"删掉了"，可能会产生新的可出发点，所以要入队，这里我想尽量让和cur邻接的顶点也挨着输出，就不使用接口Queue了，让邻接的可出发点加在队首(双指针链表)；
					q.addFirst(v); 
			}
		}
		
		if(ret.size() < g.getV()) {  //如果图里有孤立点 或者 孤立点这样的分支 是并不影响的，初始都会被扫描到 可出发点队列里，每一个这样的分支都会得到同样的处理，可以测试ug.txt；
			ret.clear();			//而只有出现环了，才会导致ret.size达不到V，即走到环那里就卡死了，因为循环依赖 谁的入度都不会为0；
			hasCycle = true;
		}
		
	}
	
	public boolean hasCycle() {  //输出[]，也有可能是 空图 导致的，并不能说明有环；
		return hasCycle;
	}
	
	public ArrayList<Integer> result() {
		return ret;
	}
	
	public static void main(String[] args) {

		Graph_final_try g = new Graph_final_try("ug.txt", true);
		TopoSort_try topoSort = new TopoSort_try(g);
		System.out.println(topoSort.result());
		System.out.println(topoSort.hasCycle());
	}

}
